282 HISTORY OF THE THEORY OF NUMBERS. [CHAP.X Let S'(ri) be the sum of the odd divisors of n, and Cn be the number of all combinations without repetitions with the sum n, so that C7 = 5. Then D(ri) = -D(n-l) -D(n-3)-D(n-6)- ..., D(n) = /S'(n) -S(n). A complicated recursion formula for r(n)is derived from log{(l-aO(l-«')*(!-a8)*. ..}==-£ -r(n)of. n* in-Complicated recursion formulas are found for the number of integers <m not factors of m, and for the sum of these integers. A recursion formula for the sum sr(ri) of the divisors ^r of n is obtained by expanding log {l-z)(l-z2).. .(1-af)} = - S isr(n)a;n. n«l?l Jacobi16 proved (1). Dirichlet17 obtained approximations to T(n). An integer s^n occurs in as many terms of this sum as there are multiples of s among 1, 2,..., n. The number of these multiples is [n/s], the greatest integer ^n/s. Hence This sum is approximately the product of n by Hence T(ri) is of the same order of magnitude as n log n. Let Ai be the least integer gz^/n and set ?==[n//i]. Then if 0(2) is any function and G(x) =0(1) +0(2) + . . . s of r5 «.i LLs In particular, if 0(s) = 1, Giving to [n/s] the approximation n/s, we see that (7) T(rc)=n log where c is of the same order of magnitude as Vn. Let p(n) be the number of distinct prime factors >1 of n. Then 2p(n) is the number of ways of factoring n into two relatively prime factors, taking "Jour, fur Math., 32, 1846, 164; 37, 1848, 67, 73. "Abhand. Ak. Wiss. Berlin, 1849, Math., 69-83; Werke, 2, 49-66. French transl., Jour, de Math., (2), 1, 1856, 353-370.